package ToYesterday.Day07;


public class reorderList {
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
        ListNode p1 = new ListNode(4);
        ListNode p2 = new ListNode(2);
        ListNode p3 = new ListNode(1);
        ListNode p4 = new ListNode(3);
        ListNode p5 = new ListNode(5);
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;

        p1 = reorder(p1);
        while (p1!=null){
            System.out.println(p1.val);
            p1 = p1.next;
        }

    }

    public static ListNode reorder(ListNode head){
        ListNode first=head;
        ListNode second = null;
        ListNode third = null;
        if (head==null||head.next==null) return head;
        //testupload
        if (head!=null) second= head.next;
        if (head.next!=null) third = head.next.next;
        first.next=null;
        while (third!=null){
            second.next = first;
            first = second;
            second = third;
            third = third.next;
        }
        second.next = first;
        return second;
    }
}
